class Solution {
public:

void digui(vector<int> nums,int i,vector<int>& A,set<vector<int>> &S,set<int> flag)
{
    vector<int> C;//因为A是引用的容器，如果插入set前sort了，那所有回溯结果都会乱套。
    if(!nums.empty())
    {
        //把第i个位置的push进去然后删掉
        if(flag.count(nums[i])>0)
        {
            return;
        }
        A.push_back(nums[i]);

        nums.erase(nums.begin()+i);
        if(!nums.empty())
        {
            for(int j=0;j<nums.size();j++)
            {
                //cout<<j<<" "<<nums.size()<<endl;

                digui(nums,j,A,S,flag);
            }
            //print_vector(A);
            C=A;
            sort(C.begin(),C.end());
            
            S.insert(C);

            A.pop_back();
        }
        else
        {

                        //print_vector(A);
            C=A;
            sort(C.begin(),C.end());

            S.insert(C);
            A.pop_back();
           
        }
    }
     else
        {

            //print_vector(A);
            C=A;
            sort(C.begin(),C.end());

            S.insert(C);
            A.pop_back();
            

        }

}
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        
        vector<vector<int>> B;
        vector<int> A;
        set<vector<int>> S;

        int i;
        //先对原vector排个序,
        sort(nums.begin(),nums.end());
        //每轮起点在回溯中出现就马上中止
        set<int> flag;

        for(i=0;i<nums.size();i++)
        {
            if(i==0||nums[i]!=nums[i-1])
            {
                digui(nums,i,A,S,flag);
                //第i个元素已经巡查过
                flag.insert(nums[i]);
                A.clear();
            }
        }
        
        for(auto j:S)
        {
            B.push_back(j);
        }
        //因为最后要加个空集，干脆充分利用A
        A.clear();
        B.push_back(A);
        return B;
    }
};